{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Chunks To Make Sorted II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxChunksToSorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多能完成排序的块 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 。</p>\n",
    "\n",
    "<p>将 <code>arr</code> 分割成若干 <strong>块</strong> ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。</p>\n",
    "\n",
    "<p>返回能将数组分成的最多块数？</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [5,4,3,2,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "将数组分成2块或者更多块，都无法得到所需的结果。 \n",
    "例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。 \n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,1,3,4,4]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "可以把它分成两块，例如 [2, 1], [3, 4, 4]。 \n",
    "然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-chunks-to-make-sorted-ii](https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-chunks-to-make-sorted-ii](https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,3,2,1]', '[2,1,3,4,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack_max = []\n",
    "        \n",
    "        for v in arr:                       \n",
    "            if stack_max!=[] and v<stack_max[-1]:\n",
    "                head = stack_max[-1] # max at the moment\n",
    "                while stack_max and v<stack_max[-1]: \n",
    "                    stack_max.pop() \n",
    "                    #if current element < stack peek (previous max, each max represent a block), then merge into a single block\n",
    "                stack_max.append(head) # append the max of the newly merged block\n",
    "            else:\n",
    "                stack_max.append(v)\n",
    "                \n",
    "        return len(stack_max)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: 'List[int]') -> 'int':\n",
    "        l = sorted(arr)\n",
    "        count = 0\n",
    "        sum1, sum2 = 0, 0\n",
    "        for i in range(len(arr)):\n",
    "            sum1 += arr[i]\n",
    "            sum2 += l[i]\n",
    "            if sum1 == sum2 :\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        stack = []\n",
    "        n = arr[0]\n",
    "        for num in arr:\n",
    "            if num > n:\n",
    "                stack.append(num)\n",
    "                n = num\n",
    "            else:\n",
    "                stack.append(n)\n",
    "\n",
    "        n = arr[-1]\n",
    "        stack1 = []\n",
    "        for num in reversed(arr):\n",
    "            if num < n:\n",
    "                stack1.insert(0,num)\n",
    "                n = num\n",
    "            else:\n",
    "                stack1.insert(0,n)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(len(arr)-1):\n",
    "            if stack[i] <= stack1[i+1]:\n",
    "                ans += 1\n",
    "        # print(stack)\n",
    "        # print(stack1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        for a, b in zip(arr, sorted(arr)):\n",
    "            sum1 += a\n",
    "            sum2 += b\n",
    "            res += sum1 == sum2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        counter1 = collections.Counter()\n",
    "        counter2 = collections.Counter()\n",
    "        for a, b in zip(arr, sorted(arr)):\n",
    "            counter1[a] += 1\n",
    "            counter2[b] += 1\n",
    "            res += counter1 == counter2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        newarr = sorted(arr)\n",
    "        sarr = snewarr = pieces = 0\n",
    "        \n",
    "        for i in range(len(newarr)):\n",
    "            sarr += arr[i]\n",
    "            snewarr += newarr[i]\n",
    "            if sarr - snewarr == 0:\n",
    "                pieces += 1\n",
    "                sarr = snewarr =0\n",
    "        return pieces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    # def heapremove(self,heap,val):\n",
    "\n",
    "    def maxChunksToSorted(self, arr) -> int:\n",
    "        #找出最短的块，使得这一块的数字小于等于后面所有数字\n",
    "        #这一块的数字中最大数字比后面所有数字中最小的数字还要小(或等于)\n",
    "        #这一块用大顶堆表示，后一块用小顶堆表示，还得实现小顶堆的remove操作\n",
    "        if not arr:\n",
    "            return 0\n",
    "        res=0\n",
    "        i=0 #right最左边元素下标\n",
    "        left=[]\n",
    "        right=arr[:]\n",
    "        heapq.heapify(left)\n",
    "        heapq.heapify(right)\n",
    "        while right:\n",
    "            if not left:\n",
    "                left.append(-arr[i])\n",
    "                right=arr[i+1:]\n",
    "                heapq.heapify(right)\n",
    "                i+=1\n",
    "                res+=1\n",
    "            elif -left[0]>right[0]:\n",
    "                right=arr[i+1:]\n",
    "                heapq.heapify(right)\n",
    "                heapq.heappush(left,-arr[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                # res+=1\n",
    "                left=[]\n",
    "        return res\n",
    "# fuck=Solution()\n",
    "# print(fuck.maxChunksToSorted([2,1,3,4,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        count = collections.defaultdict(int)\n",
    "        ans = nonzero = 0\n",
    "\n",
    "        for x, y in zip(arr, sorted(arr)):\n",
    "            count[x] += 1\n",
    "            if count[x] == 0: nonzero -= 1\n",
    "            if count[x] == 1: nonzero += 1\n",
    "\n",
    "            count[y] -= 1\n",
    "            if count[y] == -1: nonzero += 1\n",
    "            if count[y] == 0: nonzero -= 1\n",
    "\n",
    "            if nonzero == 0: ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if stack and num<stack[-1]:\n",
    "                head = stack.pop()\n",
    "                while stack and num<stack[-1]:\n",
    "                    stack.pop()\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                stack.append(num)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# O(N)\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        \n",
    "        left_max = [arr[0]]\n",
    "        for num in arr[1:]:\n",
    "            left_max = left_max + [max(left_max[-1], num)]\n",
    "\n",
    "        right_min = [arr[-1]]\n",
    "        for num in arr[::-1][1:]:\n",
    "            right_min = [min(right_min[0], num)] + right_min\n",
    "\n",
    "\n",
    "        return 1 + sum([int(right_min[i+1]>=left_max[i]) for i in range(len(arr)-1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        res = 0\n",
    "        cur_max = float('-inf')\n",
    "        for i in range(len(arr) - 1):\n",
    "            cur_max = max(cur_max, arr[i])\n",
    "            if cur_max <= min(arr[i + 1:]):\n",
    "                res += 1\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for a in range(len(arr)):\n",
    "            if not stack or arr[a]>=arr[stack[-1]]:\n",
    "                stack.append(a)\n",
    "            else:\n",
    "                while len(stack)>=2 and arr[stack[-2]]>arr[a]:\n",
    "                        stack.pop(-2)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # 769题可以使用索引，即找绝对位置\n",
    "        # 本题只有相对大小，可以通过排序取相对位置，转化为[0,n-1]的区间\n",
    "        arr=sorted(enumerate(arr),key=lambda x:x[1])\n",
    "        idxs,_=zip(*arr)\n",
    "        res,m=0,-1\n",
    "        for i in range(len(idxs)):\n",
    "            m=max(m,idxs[i])\n",
    "            if m==i:res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "    \n",
    "        def split(start,end):\n",
    "            count=0\n",
    "            for i in range(start,end):\n",
    "                if max(arr[start:i+1])<=min(arr[i+1:end+1]):  return 1+split(start,i)+split(i+1,end)\n",
    "            return count\n",
    "\n",
    "        return split(0,len(arr)-1)+1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check_merge(self, group_lst: List[int]):\n",
    "        n = len(group_lst)\n",
    "        if len(group_lst) > 1:\n",
    "            for i in range(1,len(group_lst)):            \n",
    "                if min(group_lst[i])<max(group_lst[i-1]):\n",
    "                    group_lst[i-1].extend(group_lst[i])\n",
    "                    del group_lst[i]\n",
    "                    break\n",
    "        else:\n",
    "            return\n",
    "        after = len(group_lst)\n",
    "        if after==n:\n",
    "            return \n",
    "        else:\n",
    "            self.check_merge(group_lst)\n",
    "           \n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        group_lst =[]\n",
    "        cur_lst = []\n",
    "        for v in arr:\n",
    "            # 如果当前列表为空，就添加，如果不为空，判断g是否比group中存在的最后一个列表大\n",
    "            if cur_lst == []:\n",
    "                cur_lst.append(v)\n",
    "            else:\n",
    "              \n",
    "                # 此时构建第一个分组，所有分组列表为空\n",
    "                if v>=max(cur_lst):\n",
    "                    # 比当前的分组列表大，不需要添加进去，第一个分组添加进去\n",
    "                    group_lst.append(cur_lst.copy())\n",
    "                    cur_lst.clear()\n",
    "                    cur_lst.append(v)\n",
    "                else:\n",
    "                    cur_lst.append(v)             \n",
    "        # 比当前的分组列表大，并且比前一个分组的最大还小，不需要添加进去，第一个分组添加进去\n",
    "        group_lst.append(cur_lst.copy())\n",
    "        self.check_merge(group_lst)      \n",
    "        return len(group_lst)\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stk = []\n",
    "        for v in arr:\n",
    "            if not stk or v>=stk[-1]:\n",
    "                stk.append(v)\n",
    "            else:\n",
    "                mp = stk.pop()\n",
    "                while stk and stk[-1]>v:\n",
    "                    stk.pop()\n",
    "                stk.append(mp)\n",
    "        return len(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        points = []\n",
    "        for i in arr:\n",
    "            if not points or i >= points[-1]:\n",
    "                points.append(i)\n",
    "            else:\n",
    "                _max = points.pop()\n",
    "                while points and i < points[-1]:\n",
    "                    points.pop()\n",
    "                points.append(_max)\n",
    "        return len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        A = accumulate([-inf]+arr[:-1],max)\n",
    "        B = list(accumulate(arr[::-1],min))[::-1]\n",
    "        return sum(a<=b for a,b in zip(A,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def combine_dict_and_sort(idx_dict):\n",
    "    result = []\n",
    "    for key in idx_dict.keys():\n",
    "        result.extend(sorted(idx_dict[key]))\n",
    "    return result    \n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        sorted_arr = sorted(arr)\n",
    "        index_to_num_dict = {}\n",
    "        need_new_key = True\n",
    "        for i in range(len(arr)):\n",
    "            if sorted_arr[:i + 1] != combine_dict_and_sort(index_to_num_dict) + [arr[i]]:\n",
    "                if not need_new_key:\n",
    "                    index_to_num_dict[i] = index_to_num_dict[i - 1] + [arr[i]]\n",
    "                    index_to_num_dict.pop(i - 1)\n",
    "                else:\n",
    "                    index_to_num_dict[i] = [arr[i]]\n",
    "                    need_new_key = False\n",
    "                if sorted_arr[:i + 1] == combine_dict_and_sort(index_to_num_dict):\n",
    "                    need_new_key = True\n",
    "            else:\n",
    "                index_to_num_dict[i] = [arr[i]]\n",
    "                need_new_key = True\n",
    "        return len(index_to_num_dict.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList  \n",
    "        arr_sort = sorted(arr)\n",
    "        cnt = 0\n",
    "\n",
    "        m1 = SortedList([])\n",
    "        m2 = SortedList([])\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            m1.add(x)\n",
    "            m2.add(arr_sort[i])\n",
    "            if m1 == m2:\n",
    "                cnt += 1\n",
    "                m1 = SortedList([])\n",
    "                m2 = SortedList([])\n",
    "\n",
    "        return cnt   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # 每个块的最大值必须是非严格递增的\n",
    "        # 单调栈记录每个块的最大值\n",
    "        stack = []\n",
    "        for i in range(len(arr)):\n",
    "            if len(stack) == 0 or arr[i] >= arr[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                tmp = stack.pop()\n",
    "                while len(stack) > 0 and arr[i] < arr[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                stack.append(tmp)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: [int]) -> int:\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if stack and num < stack[-1]: \n",
    "                head = stack.pop()\n",
    "                while stack and num < stack[-1]: stack.pop()\n",
    "                stack.append(head)\n",
    "            else: stack.append(num)\n",
    "        return len(stack)\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        st = []\n",
    "        for x in arr:\n",
    "            if st and st[-1]>x:\n",
    "                head = st.pop()\n",
    "                while st and st[-1]>x: st.pop()\n",
    "                st.append(head)\n",
    "            else:\n",
    "                st.append(x)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        [ max] [min ] \n",
    "        \n",
    "        i\n",
    "        max_l[i]  min_r[i+1]\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        min_r = [0]*n\n",
    "        max_l = [0]*n\n",
    "\n",
    "        min_r[n-1], max_l[0] =  arr[n-1], arr[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            max_l[i] = max(max_l[i-1], arr[i])\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            min_r[i] = min(min_r[i+1], arr[i])\n",
    "        \n",
    "        # print(max_l)\n",
    "        # print(min_r)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(0, n-1):\n",
    "            if max_l[i] <= min_r[i+1]:\n",
    "                # print(i, arr[i], max_l[i], min_r[i+1])\n",
    "                res += 1\n",
    "    \n",
    "        return res + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
